package com.sheng.leetcode.year2022.month10.day26;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/10/26
 *<p>
 * 560. 和为 K 的子数组<p>
 *<p>
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [1,1,1], k = 2<p>
 * 输出：2<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [1,2,3], k = 3<p>
 * 输出：2<p>
 *<p>
 * 提示：<p>
 * 1 <= nums.length <= 2 * 10^4<p>
 * -1000 <= nums[i] <= 1000<p>
 * -10^7 <= k <= 10^7<p>
 */
public class LeetCode0560 {

    @Test
    public void test01() {
//        int[] nums = {1, 1, 1};
//        int k = 2;
//        int[] nums = {1, 2, 3};
//        int k = 3;
        int[] nums = {1, -1, 0};
        int k = 0;
        System.out.println(new Solution1().subarraySum(nums, k));
    }
}

// 1819ms，暴力破解
//class Solution1 {
//    public int subarraySum(int[] nums, int k) {
//        int count = 0;
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            int sum = 0;
//            for (int j = i; j < length; j++) {
//                sum += nums[j];
//                if (sum == k) {
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
//}

//前缀和 + 哈希表
//这是一道经典的前缀和运用题。
//统计以每一个 nums[i] 为结尾，和为 k 的子数组数量即是答案。
//我们可以预处理前缀和数组 sum（前缀和数组下标默认从 1 开始），对于求解以某一个 nums[i] 为结尾的，
//和为 k 的子数组数量，本质上是求解在 [0,i] 中，
//sum 数组中有多少个值为 sum[i + 1] − k 的数，这可以在遍历过程中使用「哈希表」进行同步记录。
//
class Solution1 {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[] sum = new int[n + 10];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        Map<Integer, Integer> map = new HashMap<>(16);
        map.put(0, 1);
        for (int i = 1; i <= n; i++) {
            int t = sum[i], d = t - k;
            ans += map.getOrDefault(d, 0);
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        return ans;
    }
}
//
//作者：宫水三叶
//链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/1528606/by-ac_oier-pttu/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
